#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
//void Sort(vector<int>& arr)
//{
//    int n = arr.size();
//    int group=n;
//    while(group>1)
//    {
//        group=group%3+1;
//        for(int i=0;i+group<n;i++)
//        {
//            int p1=i,p2=i+group;
//            int val=arr[p2];
//            while(p1>=0&&val<arr[p1])
//            {
//                arr[p2]=arr[p1];
//                p1-=group;
//                p2-=group;
//            }
//            arr[p2]=val;
//        }
//    }
//}
void Sort(vector<int>& arr)
{
    int n=arr.size();
    int group=n;
    while(group>1)
    {
        group=group%3+1;
        for(int i=0;i+group<n;i++)
        {
            int p1=i,p2=i+group;
            int val=arr[p2];
            while(p1>=0&&val<arr[p1])
            {
                arr[p2]=arr[p1];
                p1 -= group;
                p2 -= group;
            }
            arr[p2]=val;
        }
    }
}
int main()
{

    const int n=10;
    vector<int> arr(n);
    int k=10;
    srand((unsigned int)time(nullptr));
    while(k--)
    {
        for(int i=0;i<n;i++)
        {
            arr[i]=rand()%100+1;
            cout<<arr[i]<<' ';
        }
        Sort(arr);
        cout<<endl;
        for(auto val:arr) cout<<val<<' ';
        cout<<endl<<endl;
    }
    return 0;
}
